/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-08-04
 * Time: 23:22
 */
public class SingleLinkedList {
    ListNode head;  //定义的头节点
    int size;       //用于记录元素的个数，即节点个数

    //展示链表，这个方法用于测试的！
    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;   //向后遍历，一直到最后一个节点
        }
        System.out.println();
    }

    //给定初始链表方法
    public void func() {
        //创建节点
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);
        //将节点串起来
        this.head = node1;  //标记头节点
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
    }

    //得到单链表的长度方法
    public int size() {
        return this.size;
    }

    //头插法
    public void addFirst(int data) {
        ListNode cur = new ListNode(data);
        cur.next = this.head;
        head = cur;
        this.size++;
    }

    //尾插法
    public void addLast(int data) {
        ListNode cur = new ListNode(data);
        if (this.head == null){
            this.head = cur;
            this.size++;
            return;
        }else {
            ListNode pre = this.head;
            while (pre.next != null) {
                pre = pre.next;
            }
            pre.next = cur;
            this.size++;
        }
    }

    //查找是否包含数据key的方法
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //判断位置是否合法
    private void isIllegal(int index) {
        if (index < 0 || index > this.size) {
            throw new LocationException("插入位置非法！");
        }
    }
    //在任一位置插入的方法
    public void addIndex(int index,int data) {
        try {
            isIllegal(index);
            //处理在前端插入
            if (index == 0) {
                addFirst(data);
                return;
            }
            //处理在后端插入
            if (index == this.size) {
                addLast(data);
                return;
            }
            //处理中间插入
            ListNode newNode = new ListNode(data);
            ListNode pre = find(index);

            newNode.next = pre.next; //cur.next 表示插入位置的原节点
            pre.next = newNode;
            this.size++;
        }catch (LocationException e) {
            e.printStackTrace();
        }
    }
    //获取插入位置的前一个节点
    private ListNode find(int index) {
        ListNode cur = this.head;
        int k = 0;
        while (k < index - 1) {
            cur = cur.next;
            k++;
        }
        return cur;
    }

    //删除第一次出现的数据key的节点方法
    public void remove(int key) {
        //判断链表是否为空
        if (this.head == null) {
            System.out.println("链表为空，无法删除");
            return;
        }
        //判断是否有包含key的节点
        if (judgment(key)) {
            System.out.println("该链表中没有这个节点");
            return;
        }
        //第1种情况
        if (this.head.val == key) {
            this.head = this.head.next;
            this.size--;
            return;
        }
        //第2种情况
        ListNode pre = find1(key);
        pre.next = pre.next.next;
        this.size--;
    }
    //判断是否有包含key的节点的方法
    private boolean judgment(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }
    //寻址删除节点的前一个节点的方法
    private ListNode find1(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return cur;
    }

    //删除所有包含key的节点的方法
    public void removeAllKey(int key) {
        //判断链表是否为空
        if (this.head == null) {
            System.out.println("链表为空，无法删除");
            return;
        }
        //判断是否有包含key的节点
        if (judgment(key)) {
            System.out.println("该链表中没有包含" + key + "的节点");
            return;
        }
        ListNode slow = this.head;
        ListNode fast = this.head.next;
        while (fast != null) {
            if (fast.val == key) {
                fast = fast.next;
                slow.next = fast;
                this.size--;
            }else {
                slow = fast;
                fast = fast.next;
            }
        }
        //处理头节点是包含key的节点的情况
        while (this.head != null && this.head.val == key) {
            this.head = this.head.next;
            this.size--;
        }
    }

    //清空链表
    public void clear() {
        ListNode cur = this.head;
        while (cur != null) {
            ListNode curN = cur.next;
            cur.next = null;
            cur = curN;
        }
        this.head = null;
        this.size = 0;
    }
}
